package com.heapSort;

import com.maxPriorityQueue.MaxPQ;

/**
 * @author 罗俊华
 * @date 2021/5/12 - 5:47 下午
 */
public class HeapSort<Item extends Comparable<Item>> extends MaxPQ<Item> {


    public HeapSort(Item[] array) {
        Item[] moved = (Item[]) new Comparable[array.length + 1];
        /*System.arraycopy(array, 0, moved, 1, array.length);
        moved[100] = array[array.length-1];*/
        for (int i = 0; i < array.length; i++) {
            moved[i + 1] = array[i];
        }
        super.array = moved;
        super.size = array.length;

    }

    /**
     * 这么做比挨个插入堆，要快20%，不会用到上浮操作 floatUp()
     */
    public synchronized void sort() {
        int k = size / 2;
        while (k >= 1) {
//            先从右到左构造小子堆，数组中最后一个堆为 size/2（看图观察），跳过只有1个元素的堆以提高速度
            super.sink(k); //将每一个小子堆下沉，这样数组的每一个位置都已经是堆了
            k--;
        }
//      到这里，堆的构建已经完成了，但这个堆不是有序堆
        k = size;

        while (k > 1) {
//            将最后一个元素和堆顶元素交换，因为堆顶已经是最大的元素了，
            super.exchange(k, 1);

            /**
             * 父类的 delMax()相当于把堆顶元素删除，
             * 然后把堆中最后一个元素放回堆顶，再执行下沉操作，恢复剩余堆的结构。
             * 而这里是：堆顶和最后一个元素交换之后，缩小堆（k--），
             * 相当于将堆中最大的元素删除（放到了数组的末尾），然后再下沉，使得堆有序
             */
            k--;
//            交换之后执行下沉操作
            super.sink(1, k);
        }

    }

    public synchronized Item[] getSortedArray(){
        return super.array;
    }
}
